package tree;

import java.util.*;

public class Tree {
	
	private Node tree;
	private String inputString;
	private Map<Integer, Node> lookUpTable;
	
	/**
	 * Constructs an empty tree
	 */
	public Tree(String inputString, Node tree){
		this.inputString = inputString;
		this.tree = tree;
	}
	
	public Node getTree(){
		return this.tree;
	}
	
	public void printTree(){
		System.out.println(this.toString());
	}	
	
	public Node find(Node node, int index){
		return find(node, this.inputString.charAt(index));
	}
	
	public Node find(Node node, char first) {
		List<Node> children = node.getChildren();
		for(Node child : children) {
			if(first == this.inputString.charAt(child.getStartIndex())) {
				return child;
			}
		}
		return null;
	}
	
	public ScanResult fastScan(Node start, String pattern){
		Node node = start;
		int pos = 0;
		while(pos < pattern.length()) {
			Node child = find(node, pattern.charAt(pos));
			pos = pos + child.length();
			node = child;
		}
		int index = node.length() + pattern.length() - pos;
		if (index == 0) {
			index = node.length();
		}
		return new ScanResult(node, index);
	}
	
	//Slow scan the whole tree for the pattern.
	public ScanResult slowScan(String pattern) {
		return slowScan(tree, pattern);
	}
	
	//Slow scan for the pattern beginning from a specified node.
	public ScanResult slowScan(Node start, String pattern){
		if(pattern.length() == 0) {
			return new ScanResult(start, start.length(), 0);
		}
		Node node = start;
		int pos = 0;
		while(pos < pattern.length()) {
			//Find child to follow.
			Node child = find(node, pattern.charAt(pos));
			//No child equals pattern isn't in the tree
			if(child == null) {
				return new ScanResult(node, node.length(), pos);
			}
			//Label index of the child
			int labelIndex = 0;
			while(pos < pattern.length() && labelIndex < child.length()) {
				char edgeChar = this.inputString.charAt(child.getStartIndex()+labelIndex);
				char patternChar = pattern.charAt(pos);
				if(edgeChar != patternChar) {
					return new ScanResult(child, labelIndex, pos);
				}
				pos++;
				labelIndex++;
			}
			if(pos == pattern.length()) {
				return new ScanResult(child, labelIndex, pos);
			}
			node = child;
		}
		System.out.println("How the fuck did you get here?... I better throw an error.");
		throw new Error("Something is wrong with slowScan loop.. Whoops..");
	}
	
	public List<Integer> findMatchingPattern(String pattern) {
		List<Integer> hits = new ArrayList<Integer>();
		ScanResult result = slowScan(tree, pattern);
		List<Integer> leafLengths = getLengthToLeaves(result.getLower(), -result.getIndex());
		
		if(!(result.getPatternIndex() < pattern.length())) {
			for(int length : leafLengths) {
				hits.add(this.inputString.length() - length - pattern.length() + 1);
			}
		}
		Collections.sort(hits);
		return hits;
	}
	
	public List<Integer> getLengthToLeaves(Node node, int prefixlength) {
		List<Integer> result = new ArrayList<Integer>();
		if(node.isLeaf()) {
			result.add(prefixlength + node.length());
			return result;
		} else {
			for(Node child : node.getChildren()) {
				result.addAll(getLengthToLeaves(child, prefixlength + node.length()));
			}
		}
		return result;
	}
	
	public Map<Integer, Node> getMap(){
		return lookUpTable;
	}

	public void makeLookupTable(){
		lookUpTable = new HashMap<Integer, Node>();
		tree.makeLookupTable(tree.getLeafList(new ArrayList<Node>()), lookUpTable);
//		System.out.println(lookUpTable);
	}
	
	public List<Node> getAllInternalNodes(){
		List<Node> res = new ArrayList<Node>();
		tree.getInternalnodes(res);
		System.out.println(res.size());
		return res;
	}
	
	public String getInputString(){
		return inputString;
	}
}
